Parallel vs. Sequential Belief Propagation Decoding of LDPC Codes over GF(q) and Markov Sources

摘要

A sequential updating scheme (SUS) for belief propagation (BP) decoding ofLDPC codes over Galois fields, $GF(q)$, and correlated Markov sources isproposed, and compared with the standard parallel updating scheme (PUS). Athorough experimental study of various transmission settings indicates that theconvergence rate, in iterations, of the BP algorithm (and subsequently itscomplexity) for the SUS is about one half of that for the PUS, independent ofthe finite field size $q$. Moreover, this 1/2 factor appears regardless of thecorrelations of the source and the channel's noise model, while the errorcorrection performance remains unchanged. These results may imply on the'universality' of the one half convergence speed-up of SUS decoding.